/*
This demonstrates process synchronization (you will need to work out
how to synchronize processes given the message passing paradigm). The
dining philosophers program is a program solving a problem with
resource sharing as follows. A group of philosophers are sitting
around a dining table (formed as a circle). Between each pair of
philosophers is one fork. Occasionally, one philosopher wants to eat
and to do that he needs two forks. This means that two philosophers
sitting next to each other can not eat at the same time. You should
implement this with the following in mind:

Each philosopher is a process of its own with a behavior that is
similar to the following:

think(random())
get one fork
get other fork
eat(random()) 
drop forks
restart

Like UP3, the entire setup should be started by a single process.
Like UP3, the main program should return and make it possible to
observe the processes running.  
*/

/*
We need a waiter solution, because the philosopher processes cannot accept messages while they are sleeping. Philosophers just execute sleep() to simulate thinking, eating, etc.

Waiter solution (taken from Wikipedia)

A relatively simple solution is achieved by introducing a waiter at the table. Philosophers must ask his permission before taking up any forks. Because the waiter is aware of which forks are in use, he is able to arbitrate and prevent deadlock. When four of the forks are in use, the next philosopher to request one has to wait for the waiter's permission, which is not given until a fork has been released. The logic is kept simple by specifying that philosophers always seek to pick up their left hand fork before their right hand fork (or vice versa).

To illustrate how this works, consider the philosophers are labelled clockwise from A to E. If A and C are eating, four forks are in use. B sits between A and C so has neither fork available, whereas D and E have one unused fork between them. Suppose D wants to eat. Were he to take up the fifth fork, deadlock becomes likely. If instead he asks the waiter and is told to wait, we can be sure that next time two forks are released there will certainly be at least one philosopher who could successfully request a pair of forks. Therefore deadlock cannot happen.
*/

//for printf
#include <stdlib.h>
#include <stdio.h>

//for sleep
#include <unistd.h> 

//for memcpy
#include <string.h>

//POSIX Message Passing
#include <sys/ipc.h>
#include <sys/msg.h>

#include "eat.h"

int main(int argc, char* argv){

  //The message length is constant for all messages sent in the program
  int msg_len = sizeof(msg_send) - sizeof(long); 
  //We don't use this priority concept, all priorities are 1
  msg_send.priority = 1; 

  //parent_pid
  int parent_pid = getpid();

  //loop counters
  int i,j;

  //Every Philosopher gets an id, which ranges from 1 to NUM_PHILO, the coordinator has id = 0
  int philo_id = 0;

  /*
    The parent needs to remeber all msg_box ids or pids in PORN-OS
    This matrix will simplify to a vector with all the pids in PORN-OS.
   */
  int pid_msqid_map[NUM_PHILO][2];


  //create philosophers
  //this process will be the waiter/coordinator
  for(philo_id=1; philo_id<=NUM_PHILO; philo_id++){

    int fork_res = fork();
      
      if(fork_res == 0){
	
	//child creates it's message box
	pid_msqid_map[philo_id][0] = getpid();
	pid_msqid_map[philo_id][1] = msgget(PARENT_MSG_QUEUE_ID+philo_id, 0600 | IPC_CREAT);

	break;
	
      }else{
	
	//parent remembers child's pid and msg_box id
	pid_msqid_map[philo_id][0] = fork_res; //this element is never used in this program, but will be in PORN-OS
	pid_msqid_map[philo_id][1] = msgget(PARENT_MSG_QUEUE_ID+philo_id, 0600 | IPC_CREAT);
      }
  }
 
  //create the coordinator's message box
  pid_msqid_map[0][0] = parent_pid;
  pid_msqid_map[0][1] = msgget(PARENT_MSG_QUEUE_ID, 0600 | IPC_CREAT);
 
  if(getpid() == parent_pid)
    philo_id = 0;
 //Remark: Do not overwrite philo_id in the later course of this program
 

  if(getpid() == parent_pid){
    
    /*
      fork bookkeeping: the parent will serve as waiter/coordinator,
      therefore it needs to have an overview, whether a fork is in use
      or not

      -1 : vain
      0  : fork available
      1  : fork taken

    */
    int fork_in_use[NUM_PHILO+1];

    for(i=1; i<=NUM_PHILO; i++){
      fork_in_use[i] = 0;
    }

    /*
      the 0-element is 'vain', we don't need it, but have to allocate
      it, to make the logic simpler
    */
    fork_in_use[0] = -1; 

    /*TODO: 
      We need to buffer all request that presently can not be
      satisfied. And always check if a request in this buffer can be
      granted after receiving a message from a philosopher. It is important to do this
      only after receiving a message to prevent senseless spinning.
    */
    
    struct msg recv_buffer[COORD_RCV];

    /*
      init: to indicate that an entry in this buffer is not used we set
      the priority to 0.
    */
    for(j = 0; j < COORD_RCV; j++){
      recv_buffer[j].priority = 0 ;
    }

    /*TODO: The MP does not work as it should. Can someone help me
      with this. We either get philosophers receiving messages that
      should not exist or the program hangs, probably because messages
      are lost.*/

    for(j=0; j < COORD_RCV; j++){

      printf("coordinator: iteration %d\n", j);

      //receive request
      int msg_ret_rcvreq = msgrcv(pid_msqid_map[philo_id][1], &msg_recv, msg_len, 1, 0);
      
      switch(msg_recv.msg_code){

      case MSG_REQ_FORK:
	
	printf("coordinator: received fork request(%d) from %d for fork %d\n", msg_ret_rcvreq, msg_recv.philo_id_sender, msg_recv.fork_id);
	
	if(fork_in_use[msg_recv.fork_id] == 0){
	  
	  //mark fork as in use
	  fork_in_use[msg_recv.fork_id] == 1;
	  
	  //grant request
	  
	  //prepare grant message
	  msg_send.priority = 1;
	  msg_send.philo_id_sender = 0;
	  msg_send.philo_id_receiver = msg_recv.philo_id_receiver;
	  msg_send.fork_id = msg_recv.fork_id;
	  msg_send.msg_code = MSG_GRT_FORK;

	  int msg_ret_frkgrt = msgsnd(pid_msqid_map[msg_recv.philo_id_sender][1] , &msg_send, msg_len, 0);
	  printf("coordinator: granted fork request(%d) from %d, msqbox id=%d\n", msg_ret_frkgrt, msg_send.philo_id_sender, pid_msqid_map[msg_recv.philo_id_sender][1]);
	  
	}else{
	  
	  //buffer request
	  int smallest_index_not_used = 0;
	  while(recv_buffer[smallest_index_not_used].priority == 0)
	    smallest_index_not_used++;

	  memcpy(&recv_buffer[smallest_index_not_used], &msg_recv, sizeof(msg_recv));

	}

	  break;
      case MSG_RET_FORK:

	printf("coordinator: fork %d was returned by philosopher %d\n", msg_recv.fork_id, msg_recv.philo_id_sender);

	fork_in_use[msg_recv.fork_id] = 0;

	//it might be possible to serve a request from the buffer now
	int k=0;
	for(k =1; k <= NUM_PHILO; k++){
	  
	  if(recv_buffer[k].priority != 0 && fork_in_use[recv_buffer[k].fork_id] == 0){

	    //grant request
	    
	    //prepare grant message
	    msg_send.priority = 1;
	    msg_send.philo_id_sender = 0;
	    msg_send.philo_id_receiver = recv_buffer[k].philo_id_receiver;
	    msg_send.fork_id = recv_buffer[k].fork_id;
	    msg_send.msg_code = MSG_GRT_FORK;
	    
	    int msg_ret_frkgrt = msgsnd(pid_msqid_map[recv_buffer[k].philo_id_sender][1] , &msg_send, msg_len, 0);
	    printf("coordinator: granted fork request(%d) from %d, msqbox id=%d\n", msg_ret_frkgrt, recv_buffer[k].philo_id_sender, pid_msqid_map[recv_buffer[k].philo_id_sender][1]);
	    
	    //invalidate buffer
	    recv_buffer[k].priority = 0;

	  }

	}


	break;
      default:
	printf("coordinator: Communication Failure\n");
	break;
      
      }


    }
    printf("coordinator: all messages are exchanged\n");
    //wait for all children to terminate
    for(j=0; j < NUM_PHILO; j++){
      wait();
      /*
	Remark: Remove message queues In proper programming this would
	be done here. I won't waste time with it, because it has no
	equivalent in PORN-OS.
       */
    }
    
    exit(0);

  }
  
  /*
    Philosopher Code
    The following code simulates the philosopher's behavior.
   */

  printf("philosopher %d: Joined, msqid=%d\n", philo_id, pid_msqid_map[philo_id][1]);

  //We need some pseudo random numbers per processor (sleeping, thinking)
  int r1 = abs(( get_random(M_W + getpid(), M_Z + getpid()) ) % 5) + 1;
  int r2 = abs(( get_random(M_Z + getpid(), M_W + getpid())  ) % 5) + 1;
  int r3 = abs(( get_random(M_W + getpid() + r1, M_Z + getpid()+ r2)   ) % 5) + 1;
  
  //remember which forks a process wants to simplify the logic
  int f1,f2;

  for(j=0; j < THE_CYCLES; j++){

    /*
      The philosopher is thinking for a random amount of time
    */
    sleep(r1);

    /*
      The philosopher is hungry and tries to pick up the forks
    */
    
    //prepare the message to request the first fork

    //some logic to figure out which fork a philosopher wants (odd, even stuff)
    if(philo_id == 1){ //first philosopher
      f1 = msg_send.fork_id = 1;
    }
    
    if(philo_id == NUM_PHILO && //last philosopher (odd case)
       NUM_PHILO % 2 == 1){ 
      f1 = msg_send.fork_id = NUM_PHILO;
    }

    if(philo_id == NUM_PHILO && 
       NUM_PHILO % 2 == 0){ //last philosopher (even case)
      f1 = msg_send.fork_id = 1;
    }
    
    if(philo_id != 1 && 
       philo_id != NUM_PHILO &&
       philo_id % 2 == 1){ // odd philosopher
      
      f1 = msg_send.fork_id = philo_id;
    
    }
        
    if(philo_id != 1 && 
       philo_id != NUM_PHILO &&
       philo_id % 2 == 0){ //even philosopher
      
      f1 = msg_send.fork_id = philo_id + 1;
	
    }

    //prepare message
    msg_send.priority = 1;
    msg_send.philo_id_sender = philo_id;
    msg_send.philo_id_receiver = 0;
    msg_send.msg_code = MSG_REQ_FORK;

    //send request for first fork
    printf("philosopher %d: Requesting fork %d\n", philo_id, msg_send.fork_id);
    int msg_fork_req = msgsnd(pid_msqid_map[0][1] , &msg_send, msg_len, 0);

    //wait for reply
    int msg_recv_fork = msgrcv(pid_msqid_map[philo_id][1], &msg_recv, msg_len, 1, 0);

    if(msg_recv.msg_code != MSG_GRT_FORK || msg_recv.fork_id != f1){
      
      printf("philosopher %d: Communication Failure\n", philo_id);
      printf("philosopher %d: wrong msgcode=%c, wrong fork id=%d, stupid sender=%d, intended receiver= %d\n", philo_id ,msg_recv.msg_code, msg_recv.fork_id, msg_recv.philo_id_sender, msg_recv.philo_id_receiver);
      exit(0);
    }

    printf("philosopher %d: Request for fork %d was granted\n", philo_id, msg_send.fork_id);

    //TODO: Merge this if-monster with the one above, store results in f1,f2
    if(philo_id == 1){ //first philosopher
      f2 = msg_send.fork_id = 2;
    }
    
    if(philo_id == NUM_PHILO && //last philosopher (odd case)
       NUM_PHILO % 2 == 1){ 
      f2 = msg_send.fork_id = 1;
    }

    if(philo_id == NUM_PHILO && 
       NUM_PHILO % 2 == 0){ //last philosopher (even case)
      f2 = msg_send.fork_id = NUM_PHILO;
    }
    
    if(philo_id != 1 && 
       philo_id != NUM_PHILO &&
       philo_id % 2 == 1){ // odd philosopher
      
      f2 = msg_send.fork_id = philo_id + 1;
    
    }
        
    if(philo_id != 1 && 
       philo_id != NUM_PHILO &&
       philo_id % 2 == 0){ //even philosopher
      
      f2 = msg_send.fork_id = philo_id;
	
    }

    //prepare message
    msg_send.philo_id_sender = philo_id;
    msg_send.philo_id_receiver = 0;
    msg_send.priority = 1;
    msg_send.msg_code = MSG_REQ_FORK;

    //send request for second fork
    printf("philosopher %d: Requesting fork %d\n", philo_id, msg_send.fork_id);
    int msg_fork2_req = msgsnd(pid_msqid_map[0][1] , &msg_send, msg_len, 0);

    //wait for reply
    int msg_fork2_recv = msgrcv(pid_msqid_map[philo_id][1], &msg_recv, msg_len, 1, 0);

    if(msg_recv.msg_code != MSG_GRT_FORK || msg_recv.fork_id != f2){
      printf("philosopher %d: Communication Failure\n", philo_id);
      printf("philosopher %d: wrong msgcode=%c, wrong fork id=%d, stupid sender=%d, intended receiver=%d\n", philo_id ,msg_recv.msg_code, msg_recv.fork_id, msg_recv.philo_id_sender, msg_recv.philo_id_receiver);
      exit(0);
    }

    printf("philosopher %d: Request for fork %d was granted\n", philo_id, msg_send.fork_id);
    //TODO: Do we need to check the content of the message?

    /*
      The philosopher is eating for a random amount of time
    */
    printf("philosopher %d: Eating\n", philo_id);
    sleep(r3);

    //return fork
    msg_send.msg_code = MSG_RET_FORK;

    msg_send.fork_id = f1;
    printf("philosopher %d: Returning fork %d\n", philo_id, msg_send.fork_id);
    int msg_fork_ret = msgsnd(pid_msqid_map[0][1] , &msg_send, msg_len, 0);

    msg_send.fork_id = f2;
    printf("philosopher %d: Returning fork %d\n", philo_id, msg_send.fork_id);
    int msg_fork2_ret = msgsnd(pid_msqid_map[0][1] , &msg_send, msg_len, 0);

  }

  printf("philosopher %d: I'm done\n", philo_id);

  //exit(0);

}



